<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>「力扣」第 69 题：x 的平方根（简单） | 算法不好玩</title>
    <meta name="generator" content="VuePress 1.8.2">
    <link rel="icon" href="/book/logo.png">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/github-markdown-css/2.10.0/github-markdown.min.css">
    <meta name="description" content="">
    
    <link rel="preload" href="/book/assets/css/0.styles.e159a327.css" as="style"><link rel="preload" href="/book/assets/js/app.a4355b0d.js" as="script"><link rel="preload" href="/book/assets/js/2.ba785ee6.js" as="script"><link rel="preload" href="/book/assets/js/10.b6950be1.js" as="script"><link rel="prefetch" href="/book/assets/js/11.f4ee7d6e.js"><link rel="prefetch" href="/book/assets/js/12.50fe1ace.js"><link rel="prefetch" href="/book/assets/js/13.42356fcc.js"><link rel="prefetch" href="/book/assets/js/14.e740c742.js"><link rel="prefetch" href="/book/assets/js/15.05c628f7.js"><link rel="prefetch" href="/book/assets/js/16.bd9bc9d5.js"><link rel="prefetch" href="/book/assets/js/17.e120b4fc.js"><link rel="prefetch" href="/book/assets/js/18.398213f8.js"><link rel="prefetch" href="/book/assets/js/19.e29ad0b2.js"><link rel="prefetch" href="/book/assets/js/20.14e30c1c.js"><link rel="prefetch" href="/book/assets/js/21.4f05f6c9.js"><link rel="prefetch" href="/book/assets/js/22.98fbf199.js"><link rel="prefetch" href="/book/assets/js/23.285387f4.js"><link rel="prefetch" href="/book/assets/js/24.852addbe.js"><link rel="prefetch" href="/book/assets/js/25.d30ade13.js"><link rel="prefetch" href="/book/assets/js/26.23dfa040.js"><link rel="prefetch" href="/book/assets/js/27.b6eae7df.js"><link rel="prefetch" href="/book/assets/js/28.97878b08.js"><link rel="prefetch" href="/book/assets/js/29.7217a3d0.js"><link rel="prefetch" href="/book/assets/js/3.f0c15194.js"><link rel="prefetch" href="/book/assets/js/30.0ced5a5a.js"><link rel="prefetch" href="/book/assets/js/31.8f432033.js"><link rel="prefetch" href="/book/assets/js/32.aac9aa62.js"><link rel="prefetch" href="/book/assets/js/33.db835477.js"><link rel="prefetch" href="/book/assets/js/34.a1a59c2a.js"><link rel="prefetch" href="/book/assets/js/35.ed2ef96b.js"><link rel="prefetch" href="/book/assets/js/36.48099c55.js"><link rel="prefetch" href="/book/assets/js/37.32827612.js"><link rel="prefetch" href="/book/assets/js/38.58abec0e.js"><link rel="prefetch" href="/book/assets/js/39.f6eb3874.js"><link rel="prefetch" href="/book/assets/js/4.13ea3b32.js"><link rel="prefetch" href="/book/assets/js/40.80523ed8.js"><link rel="prefetch" href="/book/assets/js/41.f7b72b7a.js"><link rel="prefetch" href="/book/assets/js/42.44e40de9.js"><link rel="prefetch" href="/book/assets/js/43.065f077f.js"><link rel="prefetch" href="/book/assets/js/44.386d9aea.js"><link rel="prefetch" href="/book/assets/js/45.d8a88f16.js"><link rel="prefetch" href="/book/assets/js/46.33bc2083.js"><link rel="prefetch" href="/book/assets/js/47.e7767237.js"><link rel="prefetch" href="/book/assets/js/48.9bb76138.js"><link rel="prefetch" href="/book/assets/js/49.c2ca5c29.js"><link rel="prefetch" href="/book/assets/js/5.32eda204.js"><link rel="prefetch" href="/book/assets/js/50.1242fe24.js"><link rel="prefetch" href="/book/assets/js/51.e8f8117d.js"><link rel="prefetch" href="/book/assets/js/52.eae5648f.js"><link rel="prefetch" href="/book/assets/js/53.39876d83.js"><link rel="prefetch" href="/book/assets/js/6.1c662163.js"><link rel="prefetch" href="/book/assets/js/7.29470445.js"><link rel="prefetch" href="/book/assets/js/8.814b737f.js"><link rel="prefetch" href="/book/assets/js/9.d4211262.js">
    <link rel="stylesheet" href="/book/assets/css/0.styles.e159a327.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/book/" class="home-link router-link-active"><!----> <span class="site-name">算法不好玩</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/book/" class="nav-link">
  主页
</a></div><div class="nav-item"><a href="/book/guide/" class="nav-link">
  关于我
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="基础算法与数据结构" class="dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow down"></span></button> <button type="button" aria-label="基础算法与数据结构" class="mobile-dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          排序算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link router-link-active">
  第 1 章 二分查找
</a></li><li class="dropdown-subitem"><a href="/book/algs/recursion/" class="nav-link">
  第 2 章 递归
</a></li></ul></li><li class="dropdown-item"><h4>
          数组里的算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link router-link-active">
  第 4 章 滑动窗口
</a></li><li class="dropdown-subitem"><a href="/book/algs/02-basic-sorting/" class="nav-link">
  第 5 章 双指针
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="威威道来" class="dropdown-title"><span class="title">威威道来</span> <span class="arrow down"></span></button> <button type="button" aria-label="威威道来" class="mobile-dropdown-title"><span class="title">威威道来</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/book/talk-show/2021-04/" class="nav-link">
  2021 年 4 月
</a></li></ul></div></div><div class="nav-item"><a href="https://leetcode-cn.com/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  力扣
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://gitee.com/liweiwei1419/book/pages" target="_blank" rel="noopener noreferrer" class="nav-link external">
  Gitee 部署页面
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"><div class="nav-item"><a href="/book/" class="nav-link">
  主页
</a></div><div class="nav-item"><a href="/book/guide/" class="nav-link">
  关于我
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="基础算法与数据结构" class="dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow down"></span></button> <button type="button" aria-label="基础算法与数据结构" class="mobile-dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          排序算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link router-link-active">
  第 1 章 二分查找
</a></li><li class="dropdown-subitem"><a href="/book/algs/recursion/" class="nav-link">
  第 2 章 递归
</a></li></ul></li><li class="dropdown-item"><h4>
          数组里的算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link router-link-active">
  第 4 章 滑动窗口
</a></li><li class="dropdown-subitem"><a href="/book/algs/02-basic-sorting/" class="nav-link">
  第 5 章 双指针
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="威威道来" class="dropdown-title"><span class="title">威威道来</span> <span class="arrow down"></span></button> <button type="button" aria-label="威威道来" class="mobile-dropdown-title"><span class="title">威威道来</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/book/talk-show/2021-04/" class="nav-link">
  2021 年 4 月
</a></li></ul></div></div><div class="nav-item"><a href="https://leetcode-cn.com/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  力扣
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://gitee.com/liweiwei1419/book/pages" target="_blank" rel="noopener noreferrer" class="nav-link external">
  Gitee 部署页面
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div> <!----></nav>  <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading"><span>第 1 章 二分查找</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/book/algs/01-binary-search/" aria-current="page" class="sidebar-link">0. 前言</a></li><li><a href="/book/algs/01-binary-search/1-1-binary-search.html" class="sidebar-link">1. 二分查找的基本问题</a></li><li><a href="/book/algs/01-binary-search/2-expansion.html" class="sidebar-link">2. 二分查找的问题变种</a></li><li><a href="/book/algs/01-binary-search/3-divide-the-search-area-into-two-parts.html" class="sidebar-link">3. 把待搜索区间分成两个部分（重点、最重要的部分在这里）</a></li><li><a href="/book/algs/01-binary-search/4-example-explanation.html" class="sidebar-link">4. 例题讲解：「力扣」第 35 题：搜索插入位置</a></li><li><a href="/book/algs/01-binary-search/5-comparison-of-two-writing-methods.html" class="sidebar-link">5. 两种写法对比</a></li><li><a href="/book/algs/01-binary-search/6-some-details.html" class="sidebar-link">6. 一些细节（以问答形式呈现）</a></li><li><a href="/book/algs/01-binary-search/7-practice.html" class="sidebar-link">7. 练习</a></li></ul></section></li><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>二分查找习题集</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/book/algs/01-binary-search/0633-sum-of-square-numbers.html" class="sidebar-link">「力扣」第 633 题：平方数之和（中等）</a></li><li><a href="/book/algs/01-binary-search/0069-sqrtx.html" aria-current="page" class="active sidebar-link">「力扣」第 69 题：x 的平方根（简单）</a></li><li><a href="/book/algs/01-binary-search/0875-koko-eating-bananas.html" class="sidebar-link">「力扣」第 875 题：爱吃香蕉的珂珂（中等）</a></li><li><a href="/book/algs/01-binary-search/1011-capacity-to-ship-packages-within-d-days.html" class="sidebar-link">「力扣」第 1011 题：在 D 天内送达包裹的能力（中等）</a></li><li><a href="/book/algs/01-binary-search/1552-magnetic-force-between-two-balls.html" class="sidebar-link">「力扣」第 1552 题：两球之间的磁力（中等）</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="「力扣」第-69-题-x-的平方根-简单"><a href="#「力扣」第-69-题-x-的平方根-简单" class="header-anchor">#</a> 「力扣」第 69 题：x 的平方根（简单）</h1> <p><strong>说明</strong>：本题解于 2021 年 4 月 3 日重写，精简了「二分查找」部分的描述，删去了「牛顿法」，关于「牛顿法」请见 「<a href="https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/" target="_blank" rel="noopener noreferrer">官方题解<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>」。</p> <hr> <p>11111111</p> <div class="tabs-component"><ul role="tablist" class="tabs-component-tabs"></ul> <div class="tabs-component-panels"><section aria-hidden="true" id="first-tab" role="tabpanel" class="tabs-component-panel" style="display:none;"><p><strong>markdown content</strong></p></section> <section aria-hidden="true" id="second-tab" role="tabpanel" class="tabs-component-panel" style="display:none;"><div class="language-javascript line-numbers-mode"><pre class="language-javascript"><code><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">=&gt;</span> <span class="token punctuation">{</span>
  console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span><span class="token string">'JavaScript code example'</span><span class="token punctuation">)</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div></section></div></div> <div class="tabs-component"><ul role="tablist" class="tabs-component-tabs"></ul> <div class="tabs-component-panels"><section aria-hidden="true" id="title" role="tabpanel" class="tabs-component-panel" style="display:none;"><p><strong>markdown content</strong></p></section> <section aria-hidden="true" id="javascript" role="tabpanel" class="tabs-component-panel" style="display:none;"><div class="language-javascript line-numbers-mode"><pre class="language-javascript"><code><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">=&gt;</span> <span class="token punctuation">{</span>
  console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span><span class="token string">'Javascript code example'</span><span class="token punctuation">)</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div></section></div></div> <p>本题是二分查找的典型应用场景：查找一个有确定范围的整数，根据 <strong>单调性</strong> 逐渐缩小搜索范围。</p> <h4 id="方法-二分查找"><a href="#方法-二分查找" class="header-anchor">#</a> 方法：二分查找</h4> <p><strong>思路分析</strong>：</p> <p><strong>分析单调性</strong>：注意到题目中给出的例 2，小数部分将被舍去。我们就知道了，如果一个数 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-math></mjx-container> 的平方大于 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi></mjx-math></mjx-container> ，那么 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-math></mjx-container> 一定不是 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi></mjx-math></mjx-container> 的平方根。我们下一轮需要在 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mo class="mjx-n"><mjx-c c="["></mjx-c></mjx-mo><mjx-mn class="mjx-n"><mjx-c c="0"></mjx-c><mjx-c c="."></mjx-c></mjx-mn><mjx-mo class="mjx-n"><mjx-c c="."></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi><mjx-mo space="3" class="mjx-n"><mjx-c c="2212"></mjx-c></mjx-mo><mjx-mn space="3" class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn><mjx-mo class="mjx-n"><mjx-c c="]"></mjx-c></mjx-mo></mjx-math></mjx-container> 区间里继续查找 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi></mjx-math></mjx-container> 的平方根。</p> <p><strong>参考代码</strong>：</p> <div class="language-Java [] line-numbers-mode"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>

    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">mySqrt</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 特殊值判断</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>x <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>x <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">int</span> left <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> right <span class="token operator">=</span> x <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">;</span>
        <span class="token comment">// 在区间 [left..right] 查找目标元素</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>left <span class="token operator">&lt;</span> right<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">int</span> mid <span class="token operator">=</span> left <span class="token operator">+</span> <span class="token punctuation">(</span>right <span class="token operator">-</span> left <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">;</span>
            <span class="token comment">// 注意：这里为了避免乘法溢出，改用除法</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>mid <span class="token operator">&gt;</span> x <span class="token operator">/</span> mid<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token comment">// 下一轮搜索区间是 [left..mid - 1]</span>
                right <span class="token operator">=</span> mid <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                <span class="token comment">// 下一轮搜索区间是 [mid..right]</span>
                left <span class="token operator">=</span> mid<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> left<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br></div></div><p><strong>代码解释</strong>：</p> <ul><li>直觉上一个数的平方根一定不会超过它的一半，但是有特殊情况，因此解方程 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-msup><mjx-mrow><mjx-mo class="mjx-lop"><mjx-c c="("></mjx-c></mjx-mo><mjx-mfrac><mjx-frac><mjx-num><mjx-nstrut></mjx-nstrut><mjx-mrow size="s"><mjx-mpadded><mjx-block style="margin:0.896em 0 0.313em;"><mjx-mrow></mjx-mrow></mjx-block></mjx-mpadded><mjx-mstyle style="font-size:141.4%;"><mjx-TeXAtom><mjx-mi class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-mstyle></mjx-mrow></mjx-num><mjx-dbox><mjx-dtable><mjx-line></mjx-line><mjx-row><mjx-den><mjx-dstrut></mjx-dstrut><mjx-mrow size="s"><mjx-mpadded><mjx-block style="margin:0.896em 0 0.313em;"><mjx-mrow></mjx-mrow></mjx-block></mjx-mpadded><mjx-mstyle style="font-size:141.4%;"><mjx-TeXAtom><mjx-mn class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-TeXAtom></mjx-mstyle></mjx-mrow></mjx-den></mjx-row></mjx-dtable></mjx-dbox></mjx-frac></mjx-mfrac><mjx-mo class="mjx-lop"><mjx-c c=")"></mjx-c></mjx-mo></mjx-mrow><mjx-script style="vertical-align:0.922em;"><mjx-mn size="s" class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-script></mjx-msup><mjx-mo class="mjx-n"><mjx-c c="2264"></mjx-c></mjx-mo><mjx-mi space="4" class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi></mjx-math></mjx-container>，得 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi><mjx-mo space="4" class="mjx-n"><mjx-c c="2264"></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="4"></mjx-c></mjx-mn></mjx-math></mjx-container>。注意到：当 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="3"></mjx-c></mjx-mn></mjx-math></mjx-container> 时，返回 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mn class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="3"></mjx-c></mjx-mn><mjx-TeXAtom><mjx-mo class="mjx-n"><mjx-c c="/"></mjx-c></mjx-mo></mjx-TeXAtom><mjx-mn class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-math></mjx-container>，当 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="4"></mjx-c></mjx-mn></mjx-math></mjx-container> 时，返回 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mn class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="4"></mjx-c></mjx-mn><mjx-TeXAtom><mjx-mo class="mjx-n"><mjx-c c="/"></mjx-c></mjx-mo></mjx-TeXAtom><mjx-mn class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-math></mjx-container>。因此只需要对 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="0"></mjx-c></mjx-mn></mjx-math></mjx-container> 和 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn></mjx-math></mjx-container> 作单独判断。其它情况下，搜索的下界 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-TeXAtom><mjx-mtext class="mjx-ty"><mjx-c c="l"></mjx-c><mjx-c c="e"></mjx-c><mjx-c c="f"></mjx-c><mjx-c c="t"></mjx-c></mjx-mtext></mjx-TeXAtom><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn></mjx-math></mjx-container>，上界 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-TeXAtom><mjx-mtext class="mjx-ty"><mjx-c c="r"></mjx-c><mjx-c c="i"></mjx-c><mjx-c c="g"></mjx-c><mjx-c c="h"></mjx-c><mjx-c c="t"></mjx-c></mjx-mtext></mjx-TeXAtom><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mi space="4" class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi><mjx-TeXAtom><mjx-mo class="mjx-n"><mjx-c c="/"></mjx-c></mjx-mo></mjx-TeXAtom><mjx-mn class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-math></mjx-container>；</li> <li>使用 <code>mid &gt; x / mid</code> 作为判断条件是因为 <code>mid * mid &gt; x</code> 在 <code>mid</code> 很大的时候，<code>mid * mid</code> 有可能会整型溢出，使用 <code>mid * mid &gt; x</code> 不能通过的测试用例如下：</li></ul> <p><img src="https://pic.leetcode-cn.com/1617410699-YFxGNB-image.png" alt="image.png">{:style=&quot;width:400px&quot;}{:align=center}</p> <p><strong>复杂度分析</strong>：</p> <ul><li>时间复杂度：<mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>，每一次搜索的区间大小为原来的 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mfrac><mjx-frac><mjx-num><mjx-nstrut></mjx-nstrut><mjx-mrow size="s"><mjx-mpadded><mjx-block style="margin:0.896em 0 0.313em;"><mjx-mrow></mjx-mrow></mjx-block></mjx-mpadded><mjx-mstyle style="font-size:141.4%;"><mjx-TeXAtom><mjx-mn class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn></mjx-TeXAtom></mjx-mstyle></mjx-mrow></mjx-num><mjx-dbox><mjx-dtable><mjx-line></mjx-line><mjx-row><mjx-den><mjx-dstrut></mjx-dstrut><mjx-mrow size="s"><mjx-mpadded><mjx-block style="margin:0.896em 0 0.313em;"><mjx-mrow></mjx-mrow></mjx-block></mjx-mpadded><mjx-mstyle style="font-size:141.4%;"><mjx-TeXAtom><mjx-mn class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-TeXAtom></mjx-mstyle></mjx-mrow></mjx-den></mjx-row></mjx-dtable></mjx-dbox></mjx-frac></mjx-mfrac></mjx-math></mjx-container>，时间复杂度为 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-msub><mjx-mi noIC="true" class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-script style="vertical-align:-0.241em;"><mjx-mn size="s" class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-script></mjx-msub><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mi space="4" class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>；</li> <li>空间复杂度：<mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mn class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>。</li></ul> <hr> <h4 id="总结"><a href="#总结" class="header-anchor">#</a> 总结</h4> <h5 id="_1-为什么用-while-left-right-这种写法"><a href="#_1-为什么用-while-left-right-这种写法" class="header-anchor">#</a> 1. 为什么用 <code>while(left &lt; right)</code> 这种写法？</h5> <p>采用 <code>while(left &lt; right)</code> 这种写法，在退出循环的时候有 <code>left == right</code> 成立，因此返回 <code>left</code> 或者 <code>right</code> 都可以。不用思考返回 <code>left</code> 还是 <code>right</code>。</p> <h5 id="_2-如何想到判断条件是-mid-x-mid"><a href="#_2-如何想到判断条件是-mid-x-mid" class="header-anchor">#</a> 2. <strong>如何想到判断条件是 <code>mid &gt; x / mid</code></strong>？</h5> <p><code>while(left &lt; right)</code> 这种写法把区间分成两个区间，一个区间一定不存在目标元素，另一个区间有可能存在目标元素。因此 <strong>先思考满足什么条件的 <code>mid</code> 一定不是目标元素</strong>，进而思考下一轮搜索区间不容易出错，它的反面就是另一个区间。</p> <p>根据本题解最开始分析例 2。我们分析出：如果一个数 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-math></mjx-container> 的平方大于 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi></mjx-math></mjx-container> ，那么 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-math></mjx-container> 一定不是 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="x"></mjx-c></mjx-mi></mjx-math></mjx-container> 的平方根，这种情况下，搜索区间是 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mo class="mjx-n"><mjx-c c="["></mjx-c></mjx-mo><mjx-mn class="mjx-n"><mjx-c c="0"></mjx-c><mjx-c c="."></mjx-c></mjx-mn><mjx-mo class="mjx-n"><mjx-c c="."></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi><mjx-mo space="3" class="mjx-n"><mjx-c c="2212"></mjx-c></mjx-mo><mjx-mn space="3" class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn><mjx-mo class="mjx-n"><mjx-c c="]"></mjx-c></mjx-mo></mjx-math></mjx-container>（这里 <code>a = mid</code>，下同），这就是这种情况下我们将右边界设置为 <code>right = mid - 1</code> 的原因。剩下的情况不用思考，搜索区间一定是 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mo class="mjx-n"><mjx-c c="["></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="."></mjx-c></mjx-mo><mjx-mo space="2" class="mjx-n"><mjx-c c="."></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="r"></mjx-c></mjx-mi><mjx-mi class="mjx-i"><mjx-c c="i"></mjx-c></mjx-mi><mjx-mi class="mjx-i"><mjx-c c="g"></mjx-c></mjx-mi><mjx-mi class="mjx-i"><mjx-c c="h"></mjx-c></mjx-mi><mjx-mi class="mjx-i"><mjx-c c="t"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="]"></mjx-c></mjx-mo></mjx-math></mjx-container> ，此时设置 <code>left = mid</code>。</p> <h5 id="_3-取中间数为什么需要加-1"><a href="#_3-取中间数为什么需要加-1" class="header-anchor">#</a> 3. 取中间数为什么需要加 1？</h5> <p>这一点初学的时候很难理解（包括我自己），但其实我们只要对着错误的测试用例打印出相关变量看一下。</p> <div class="language-Java [] line-numbers-mode"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>

    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">mySqrt</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 特殊值判断</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>x <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>x <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">int</span> left <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> right <span class="token operator">=</span> x <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">;</span>
        <span class="token comment">// 在区间 [left..right] 查找目标元素</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>left <span class="token operator">&lt;</span> right<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token comment">// 取中间数 mid 下取整时</span>
            <span class="token keyword">int</span> mid <span class="token operator">=</span> left <span class="token operator">+</span> <span class="token punctuation">(</span>right <span class="token operator">-</span> left <span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">;</span>

            <span class="token comment">// 调试语句开始</span>
            <span class="token keyword">try</span> <span class="token punctuation">{</span>
                <span class="token class-name">Thread</span><span class="token punctuation">.</span><span class="token function">sleep</span><span class="token punctuation">(</span><span class="token number">1000</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">catch</span> <span class="token punctuation">(</span><span class="token class-name">InterruptedException</span> e<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                e<span class="token punctuation">.</span><span class="token function">printStackTrace</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">&quot;left = &quot;</span> <span class="token operator">+</span> left <span class="token operator">+</span> <span class="token string">&quot;, right = &quot;</span> <span class="token operator">+</span> right <span class="token operator">+</span> <span class="token string">&quot;, mid = &quot;</span> <span class="token operator">+</span> mid<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token comment">// 调试语句结束</span>

            <span class="token comment">// 注意：这里为了避免乘法溢出，改用除法</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>mid <span class="token operator">&gt;</span> x <span class="token operator">/</span> mid<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token comment">// 下一轮搜索区间是 [left..mid - 1]</span>
                right <span class="token operator">=</span> mid <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                <span class="token comment">// 下一轮搜索区间是 [mid..right]</span>
                left <span class="token operator">=</span> mid<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> left<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token class-name">Solution</span> solution <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Solution</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> x <span class="token operator">=</span> <span class="token number">9</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> res <span class="token operator">=</span> solution<span class="token punctuation">.</span><span class="token function">mySqrt</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>res<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br></div></div><p>控制台输出：</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>left = 1, right = 4, mid = 2
left = 2, right = 4, mid = 3
left = 3, right = 4, mid = 3
left = 3, right = 4, mid = 3
left = 3, right = 4, mid = 3
left = 3, right = 4, mid = 3
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br></div></div><p><strong>分析原因</strong>：<strong>在区间只有 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mn class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-math></mjx-container> 个数的时候</strong>，根据 <code>if</code>、<code>else</code> 的逻辑区间的划分方式是：<code>[left..mid - 1]</code> 与 <code>[mid..right]</code>。如果 <code>mid</code> 下取整，在区间只有 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mn class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-math></mjx-container> 个数的时候有 <code>mid = left</code>，一旦进入分支 <code>[mid..right]</code> 区间不会再缩小，发生死循环。</p> <p><strong>解决办法</strong>：把取中间数的方式成上取整。</p></div> <footer class="page-edit"><!----> <div class="last-updated"><span class="prefix">上次更新:</span> <span class="time">4/10/2021, 6:19:58 PM</span></div></footer> <div class="page-nav"><p class="inner"><span class="prev">
      ←
      <a href="/book/algs/01-binary-search/0633-sum-of-square-numbers.html" class="prev">
        「力扣」第 633 题：平方数之和（中等）
      </a></span> <span class="next"><a href="/book/algs/01-binary-search/0875-koko-eating-bananas.html">
        「力扣」第 875 题：爱吃香蕉的珂珂（中等）
      </a>
      →
    </span></p></div> </main></div><div class="global-ui"><!----></div></div>
    <script src="/book/assets/js/app.a4355b0d.js" defer></script><script src="/book/assets/js/2.ba785ee6.js" defer></script><script src="/book/assets/js/10.b6950be1.js" defer></script>
  </body>
</html>
